package ljl.alg.jianzhioffer.round3.hard;

import java.util.LinkedList;

public class _59_maxSlidingWindow {

    /**
     * 这个解法队列里存下标
     */
    class ok {
        public int[] maxSlidingWindow(int[] nums, int k) {
            int[] res = new int[nums.length - k + 1];
            // 存下标了，不然不知道长度
            LinkedList<Integer> q = new LinkedList<>();
            for (int i = 0; i < k; i++) {
                while (q.size() > 0 && nums[q.peekLast()] < nums[i]) {
                    q.pollLast();
                }
                q.offer(i);
            }
            res[0] = nums[q.peekFirst()];
            for (int i = k; i < nums.length; i++) {
                // 先入队，维护单调队列
                while (q.size() > 0 && nums[q.peekLast()] < nums[i]) {
                    q.pollLast();
                }
                q.offer(i);
                // 队首元素看情况出队
                if (i - q.peekFirst() + 1 > k)
                    q.pollFirst();
                // 剩下的队首元素最大，放到结果里
                res[i - k + 1] = nums[q.peekFirst()];
            }
            return res;
        }
    }

    /**
     * 原来不非得存下标，不存下标也行
     */
    class ok2 {
        public int[] maxSlidingWindow(int[] nums, int k) {
            int[] res = new int[nums.length - k + 1];
            LinkedList<Integer> q = new LinkedList<>();
            for (int i = 0; i < k; i++) {
                while (q.size() > 0 && q.peekLast() < nums[i]) {
                    q.pollLast();
                }
                q.offer(nums[i]);
            }
            res[0] = q.peekFirst();
            for (int i = k; i < nums.length; i++) {
                if (q.peekFirst() == nums[i - k])
                    q.pollFirst();
                while (q.size() > 0 && q.peekLast() < nums[i]) {
                    q.pollLast();
                }
                q.offerLast(nums[i]);
                res[i - k + 1] = q.peekFirst();
            }
            return res;
        }
    }

}
